package newcoder;
import java.util.*;

public class NC42 {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    int[] nums;
    int[] flag;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        this.nums=num;
        this.flag= new int[nums.length];
        dfs(new ArrayList<Integer>());
        return res;
    }
    void dfs(ArrayList<Integer> list){
        if(list.size()==nums.length){ //剪枝
            if(res.size()!=0){
                ArrayList<Integer> temp = res.get(res.size()-1);
                for(int i=0;i<nums.length;i++){
                    if(list.get(i)!=temp.get(i)){
                        res.add(new ArrayList<>(list));
                        break;
                    }
                }
            }else{
                res.add(new ArrayList<>(list));
            }

        }
        for(int i=0;i<nums.length;i++){
            if(flag[i]!=1){
                flag[i]=1;
                list.add(nums[i]);
                dfs(list);
                flag[i]=0;
                list.remove(list.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1,2,3};
        NC42 nc = new NC42();
        ArrayList<ArrayList<Integer>> res = nc.permuteUnique(a);
        System.out.println();
    }
}
